Mixed raster content (MRC) is an ITU standard (T.44) for compound document compression, where a document image is separated into multiple layers, and each layer is compressed by a specific encoder that is suitable for that layer. A typical 3-layer MRC document contains a binary mask, a foreground layer, and a background layer, where each pixel value of the mask is used to select between the foreground and background pixels in reconstructing the raster image. In general a 3-layer MRC encoder includes mask generation, data filling (foreground and background generation), foreground and background scaling, followed by separate compression of each layer.
While mask generation is critical, data filling is also very important for achieving high performance of compression. In general, a data filling method for an MRC-based encoder is required to fill in all the “don't care” pixels (i.e., irrelevant pixels for reconstruction) in both foreground and background layers. With lossless compression, “don't care” pixels affect only the bit rate. However, when lossy compression is used to obtain lower bit rates, poor choices of “don't care” pixels can change “care” pixels (i.e., relevant pixels for reconstruction) during decoding. Although “don't care” pixels are not directly relevant to the reconstruction of the image, the selection of values for these pixels may have significant impact on the rate-distortion performance of the compression. For example, suppose the don't care pixels in the foreground and background layers are filled in with a single color value. In this case, objectional ringing artifacts may occur in the decompressed image at the boundary of the foreground and background with any lossy compression such as JPEG and JPEG2000, and therefore the benefit of the MRC compression is significantly lost.
There are a number of approaches that have been proposed to solve these problems. These methods can be classified into three categories: spatial domain data fill; iterative frequency domain data fill; and mask dependent transform.
The spatial domain data fill approaches are generally simple and fast. The iterative frequency domain data fill approaches provide higher compression, but are more computationally expensive. The mask dependent transform approaches result in very high compression, but require interaction between mask and foreground/background for compression of the foreground and background layers and, thus, are not fully compliant with MRC.
More specifically there are several spatial domain data fill algorithms, some of which are described below. In one spatial domain data fill approach, multiple passes are performed in each block that contains a mixture of care and don't care pixels. In each pass, each unfilled pixel is determined by the average of the neighboring care pixels. This procedure is repeated until all “holes” are filled up. For more information, see De Querioz, “On Data-Filling Algorithms for MRC Layers,” Proc. IEEE Intl. Conf. on Image Processing, ICIP, Vancouver, Canada, Vol. II, pp. 586-589, September 2000.
Another spatial domain data fill approach performs a coder matched layer separation method that includes a single pass block-based data filling algorithm for interpolation of don't care pixels. More specifically, for each block that contains a mixture of care and don't care pixels, the values of the don't care pixels are assigned based on the average of care pixels of that block. Each don't care block is filled by either a predefined value or the average value of the previous filled block. For more information, see U.S. Pat. No. 6,941,024, entitled “Coder Matched Layer Separation and Interpolation for Compression of Compound Documents,” issued September 2005.
Another spatial domain data fill approach is implemented in LuraDocuments developed by Luratech. In this approach, foreground and background are generated at a reduced resolution by a factor of 3. In each 3×3 block that contains both care and don't care pixels, an average is taken of all care pixels except edge pixels. Then a 5×5 averaging filter is used to iteratively interpolate don't care pixels using these average values until all “holes” are filled up. This method does consider excluding edge pixels in averaging, thereby reducing ringing artifact. For more information, see Thierschmann, et al., “A Scalable DSP Architecture For High-Speed Color Document Compression,” Document Recognition and Retrieval VIII, Kantor, et al., Editors, Proceedings of SPIE Vol. 4307 (2001), San Jose, Calif., January 2001.
Multi-resolution segmentation and fill (MSF) is a multi-resolution data fill algorithm used in the wavelet domain. The method uses a “lossy edge” idea that handles the edge effect for data filling. For more information, see U.S. patent Ser. No. 10/927,323, entitled “Multi-resolution Segmentation and Fill”, filed Aug. 25, 2004.